package org.apache.commons.graph.shortestpath

import com.carrotsearch.junitbenchmarks.BenchmarkOptions
import com.carrotsearch.junitbenchmarks.BenchmarkRule
import com.carrotsearch.junitbenchmarks.annotation.AxisRange
import com.carrotsearch.junitbenchmarks.annotation.BenchmarkMethodChart
import org.apache.commons.graph.CommonsGraph.findShortestPath
import org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph
import org.apache.commons.graph.GraphException
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.WeightedPath
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.BaseLabeledWeightedEdge
import org.apache.commons.graph.model.BaseWeightedEdge
import org.apache.commons.graph.model.DirectedMutableGraph
import org.apache.commons.graph.weight.OrderedMonoid
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Assert
import org.junit.BeforeClass
import org.junit.Rule
import org.junit.Test
import java.util.*
import kotlin.math.max

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

@AxisRange(min = 0.0, max = 2.0)
@BenchmarkMethodChart(filePrefix = "dijkstras")
@BenchmarkOptions(benchmarkRounds = 10, warmupRounds = 5)
class UniVsBiDijkstraBenchmarkTestCase {
    @JvmField
    @Rule
    var benchmarkRun: BenchmarkRule = BenchmarkRule()

    @Test
    fun testPerformBidirectionalDijkstra() {
        val source = sourceListBi!!.removeFirst()
        val target = targetListBi!!.removeFirst()

        try {
            val path: WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
                findShortestPath(graph!!)
                    .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                    .from(source)
                    .to(target)
                    .applyingBidirectionalDijkstra(weightOperations!!)

            Assert.assertTrue(path.size > 0)
            Assert.assertTrue(path.weight > 0.0)
        } catch (e: Exception) {
            e.printStackTrace()
        }
    }

    @Test
    fun testPerformUnidirectionalDijkstra() {
        val source = sourceListUni!!.removeFirst()
        val target = targetListUni!!.removeFirst()

        try {
            val path: WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
                findShortestPath(graph!!)
                    .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                    .from(source)
                    .to(target)
                    .applyingDijkstra(weightOperations!!)

            Assert.assertTrue(path.size > 0)
            Assert.assertTrue(path.weight > 0.0)
        } catch (e: Exception) {
            e.printStackTrace()
        }
    }

    companion object {
        private const val NODES = 5000
        private const val EDGES = 100000

        private var graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>? = null

        private var weightedEdges: Mapper<BaseLabeledWeightedEdge<Double>, Double>? = null

        private var sourceListUni: LinkedList<BaseLabeledVertex>? = null

        private var sourceListBi: LinkedList<BaseLabeledVertex>? = null

        private var targetListUni: LinkedList<BaseLabeledVertex>? = null

        private var targetListBi: LinkedList<BaseLabeledVertex>? = null

        private var vertices: MutableList<BaseLabeledVertex>? = null

        private var weightOperations: OrderedMonoid<Double>? = null

        @JvmStatic
        @BeforeClass
        fun setUp(): Unit {
            weightOperations = DoubleWeightBaseOperations()

            weightedEdges = object : Mapper<BaseLabeledWeightedEdge<Double>, Double> {
                override fun map(input: BaseLabeledWeightedEdge<Double>): Double {
                    return input.weight
                }
            }

            graph = newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() {
                var r: Random = Random()

                fun addEdge(src: BaseLabeledVertex, dst: BaseLabeledVertex): Boolean {
                    try {
                        addEdge(
                            BaseLabeledWeightedEdge<Double>(
                                String.format("%s -> %s", src, dst),
                                10.0 * r.nextDouble() + 1.0
                            )
                        ).from(src).to(dst)
                        return true
                    } catch (e: GraphException) {
                        // ignore duplicate edge exceptions
                        return false
                    }
                }

                override fun connect() {
                    vertices = ArrayList()
                    for (i in 0..<NODES) {
                        val v = BaseLabeledVertex(i.toString())
                        addVertex(v)
                        vertices!!.add(v)
                    }

                    // form a connected graph
                    for (i in 0..<NODES - 1) {
                        addEdge(vertices!!.get(i), vertices!!.get(i + 1))
                    }

                    addEdge(vertices!!.get(NODES - 1), vertices!!.get(0))

                    // we have already created #NODES edges
                    val maxEdges = max(0.0, (EDGES - NODES).toDouble()).toInt()
                    for (i in 0..<maxEdges) {
                        while (!addEdge(vertices!!.get(r.nextInt(NODES)), vertices!!.get(r.nextInt(NODES)))) {
                            // do nothing
                        }
                    }
                }
            })

            sourceListUni = LinkedList()
            targetListUni = LinkedList()

            sourceListBi = LinkedList()
            targetListBi = LinkedList()

            val r = Random()

            for (i in 0..14) {
                val s = vertices!![r.nextInt(
                    vertices!!.size
                )]
                sourceListUni!!.add(s)
                sourceListBi!!.add(s)

                val t = vertices!![r.nextInt(
                    vertices!!.size
                )]
                targetListUni!!.add(t)
                targetListBi!!.add(t)
            }
        }
    }
}
